from typing import *


class Solution:

    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:

        def f(a, p):
            if a == 1:
                return 1
            if p == 0:
                return 1
            if p == 1:
                return a
            k = f(a, p // 2) % mod
            return k * k * pow(a, p & 1) % mod

        mod = 1000000007
        tot = 1
        for row in grid:
            for r in row:
                tot *= r
        print(f'tot{tot}')
        m, n = len(grid), len(grid[0])
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                ans[i][j] = tot * f(grid[i][j], mod - 2) % mod % 12345
        return ans


s = Solution()
print(
    s.constructProductMatrix([[1, 5, 5, 6], [4, 7, 6, 1], [2, 3, 3, 6],
                              [3, 6, 3, 7]]))
# print(s.constructProductMatrix(grid = [[12345],[2],[1]]))
# print(s.constructProductMatrix(grid=[[1, 2], [3, 4]]))

# print(6570 % 12345)
print(28764793 % 12345)
print(1028764800 % 12345)
# def f(a, p):
#     if p == 0:
#         return 1
#     if p == 1:
#         return a
#     print(a, p)
#     k = f(a, p // 2)
#     return k * k * pow(a, p & 1)

# print(f(3, 3))


class Solution:

    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        ans = [[0] * n for _ in range(m)]
        p = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                ans[i][j] = p
                p = (p * grid[i][j]) % 12345
        p = 1
        for i in range(m):
            for j in range(n):
                ans[i][j] = ans[i][j] * p % 12345
                p = (p * grid[i][j]) % 12345

        return ans
